package pers.qianyu.month_202011.date_20201122;

/**
 * 230. 二叉搜索树中第K小的元素
 * https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
 *
 * @author mizzle rain
 * @date 2020-11-22 16:28
 */
public class KthSmallest {
    private int res;
    private int k;

    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        this.k = k;
        recur(root);
        return res;
    }

    private void recur(TreeNode root) {
        if (root == null) {
            return;
        }
        recur(root.left);
        k--;
        if (k == 0) {
            res = root.val;
            return;
        }
        recur(root.right);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
